
//2948.交换得到字典序最小的数组
class Solution {
public:
    vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
        //可以先将数组进行排序，根据limit判断那一组的数字是可以进行交换的
        //但是在排序后数组就是乱序的，所以排序时要带上下标
        int n=nums.size();
        vector<pair<int,int>> tmp;
        for(int i=0;i<n;i++)
            tmp.push_back({nums[i],i});

        //对数组进行排序
        sort(tmp.begin(),tmp.end(),[](pair<int,int> x,pair<int,int> y){ return x.first<y.first;});  //只需要根据元素大小进行排序即可
        
        //使用分组循环，根据limit判断那些数字是可以进行交换的
        vector<int> ret(n);
        int i=0;
        while(i<n)
        {
            int start=i++;
            while(i<n&&tmp[i].first<=tmp[i-1].first+limit) i++;   

            //提取出[start,i)位置的下标
            vector<int> index;
            for(int j=start;j<i;j++) index.push_back(tmp[j].second);

            //对数组下标进行排序
            sort(index.begin(),index.end());
            
            //将下标和元素大小的对应关系映射到答案上
            for(int k=0;k<index.size();k++)
            ret[index[k]]=tmp[k+start].first;
        }
        return ret;
    }
};